home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BIGNUM.H < prev    next >
C/C++ Source or Header  |  1992-08-12  |  15KB  |  349 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MBN 10/24/89 -- Initial design and implementation
  14. // Updated: MJF 07/31/90 -- Added terse print
  15. // Updated: DLS 03/22/91 -- New lite version
  16. // Updated: VDN 05/01/92 -- intializer needed to create Bignums for .so libs
  17. // Updated: JAM 08/11/92 -- removed 'inline' from friend declarations
  18. //
  19. // The Bignum class implements infinite precision integer arithmetic.  A Bignum
  20. // object grows and  shrinks in size as  necessary to  accommodate its  current
  21. // value.  All of the  standard C operations defined on  integers  in Kernighan
  22. // and Ritchie,   Appendix  A carry  over  directly  to  Bignums   by means  of
  23. // overloading,  except for those  operations that  make assumptions  about the
  24. // underlying representation.   For  example, we have  not  implemented bitwise
  25. // operators &,|,^ because they would have to make assumptions about our Bignum
  26. // implementation.  On the other  hand,  we have,  for example  implemented the
  27. // operators   << and   >>,  because   these can   be always   be   interpreted
  28. // arithmetically  as multiplication  or  division   by 2, respectively, of the
  29. // underlying integer type.  The four standard arithmetic operations +,-,*, and
  30. // / utilize algorithms from Knuth, Volume 2 for efficiency.  However, the user
  31. // is warned that the  Bignum integer  arithmetic class  is  still considerably
  32. // slower than the built-in integer data types.
  33. //
  34. // The  Bignum class  implements   common  arithmetic exception  handling   and
  35. // provides  the  application  with support  for  detecting negative  infinity,
  36. // positive infinity, overflow,  and underflow as a result  of some  arithmetic
  37. // expression. If  one of these   conditions or an attempt  to  convert from  a
  38. // Bignum with no value to  a built-in type  is detected, an Error exception is
  39. // raised. The application programmer can provide an exception handler  to take
  40. // care of this problem. If  no such handler  is available, an error message is
  41. // printed and the application terminates.
  42. //
  43. // The Bignum class requires several constants be defined to  insure precision
  44. // and  accuracy of conversion.   The preprocessor  symbols  MINSHORT, MININT,
  45. // MINLONG, MAXSHORT, MAXINT, and MAXLONG  are calculated in the <COOL/misc.h>
  46. // header file via  various  bit manipulation  macros. The  symbols  MINFLOAT,
  47. // MINDOUBLE,  MAXFLOAT,  and MAXDOUBLE  are system   dependent  and cannot be
  48. // calculated.  Most systems typically have values for these constants  in the
  49. // system  header file <values.h>.  Values  for a  specific machine  should be
  50. // copied into the <COOL/misc.h> header file as necessary.
  51. //
  52. // The  private  data section of  the Bignum class  has a pointer to storage of
  53. // consecutive short  blocks large enough  to  hold the  value.  The number of
  54. // blocks is  contained in  a  private integer  slot.   The Bignum  class  also
  55. // contains a private data slot providing  arithmetic  exception status.  There
  56. // are  five constructors for the  Bignum class.  The first  is a simple inline
  57. // constructor  that initializes the state and  private data slots.  The second
  58. // takes an integer (short, int, or long)  and uses that  as  the initial value
  59. // for the object.  The third takes a real  (float or double)  and uses that as
  60. // the  initial   value for the object.    The  fourth takes  a null-termianted
  61. // character string  in either octal, decimal, hex, or exponential format   and
  62. // converts it  to the appropriate  Bignum value.   Finally,  the fifth takes a
  63. // const reference to another Bignum object and duplicates its state and value.
  64. // The Bignum class provides overloaded  operators  for addition,  subtraction,
  65. // multiplication,  division, and  modulus.  Also  available  are equality  and
  66. // inequality,  assignment, increment, decrement, unary minus, ones-complement,
  67. // output,  less than, greater than,  less than  or equal, and  greater than or
  68. // equal.  Finally, five type conversion functions to  short, int, long, float,
  69. // and double are provided.
  70. //
  71. // Use envelope to turn a deep copy into a shallow copy, when Bignums are
  72. // returned by value from operations like +,-,*,/,%,<<,>>.
  73. //
  74. // WARNINGS
  75. // JAM -- make code super portable/correct and doesn't assume anything
  76. //        about data types other than char<=short<=int<=long
  77. //
  78.  
  79. #ifndef BIGNUMH                    // If no definition for Bignum
  80. #define BIGNUMH                    // define the bignum symbol
  81.  
  82. #ifndef REGEXPH                    // If no regular expressions
  83. #include <cool/Regexp.h>            // include definition
  84. #endif
  85.  
  86.  
  87. typedef unsigned int Counter;
  88. typedef unsigned short Data;
  89.  
  90. class CoolBignumE;                // forward dec. of envelope
  91.  
  92. class CoolBignum {
  93. public:
  94.   // CoolBignum constructors
  95.   CoolBignum ();                                // Void constructor
  96.   CoolBignum (const long);            // Long constructor
  97.   CoolBignum (const char*);            // String constructor
  98.   CoolBignum (const double);            // Double constructor
  99.   CoolBignum (const CoolBignum&);        // Copy constructor 
  100.   ~CoolBignum ();                // Destructor
  101.  
  102.   // Conversion operators
  103.   operator short () const;            // Implicit type conversion
  104.   operator int () const;            // Implicit type conversion
  105.   operator long () const;            // Implicit type conversion
  106.   operator float () const;            // Implicit type conversion
  107.   operator double () const;            // Implicit type conversion
  108.  
  109.   // Overloaded operators
  110.   CoolBignumE operator- () const;               // Unary minus operator
  111.   inline Boolean operator! () const;        // Not operator
  112.  
  113.   CoolBignum& operator= (const CoolBignum&);    // Assignment operator
  114.   inline CoolBignum& operator=(CoolBignumE&);    // From envelope back to Bignum
  115.  
  116.   friend CoolBignumE operator+ (const CoolBignum&, const CoolBignum&); // Plus operator
  117.   friend CoolBignumE operator- (const CoolBignum&, const CoolBignum&); // Minus operator
  118.   friend CoolBignumE operator* (const CoolBignum&, const CoolBignum&); // Multiplication op
  119.   friend CoolBignumE operator/ (const CoolBignum&, const CoolBignum&); // Division operator
  120.   friend CoolBignumE operator% (const CoolBignum&, const CoolBignum&); // Modulus operator
  121.   friend CoolBignumE operator<< (const CoolBignum&, long l); // Arithmetic left shift
  122.   friend CoolBignumE operator>> (const CoolBignum&, long l); // Arithmetic right shift
  123.   inline CoolBignum& operator+= (const CoolBignum&);    // plus/assign
  124.   inline CoolBignum& operator-= (const CoolBignum&);    // minus/assign
  125.   inline CoolBignum& operator*= (const CoolBignum&);    // multiply/assign
  126.   inline CoolBignum& operator/= (const CoolBignum&);    // division/assign
  127.   inline CoolBignum& operator%= (const CoolBignum&);    // modulus/assign
  128.   inline CoolBignum& operator<<= (const CoolBignum&);    // left shift/assign
  129.   inline CoolBignum& operator>>= (const CoolBignum&);    // right shift/assign
  130.   
  131.   CoolBignum& operator++ ();            // increment
  132.   CoolBignum& operator-- ();            // decrement
  133.  
  134.   Boolean operator== (const CoolBignum&) const;    // equality
  135.   inline Boolean operator!= (const CoolBignum&) const; // inequality
  136.   Boolean operator< (const CoolBignum&) const;    // less than
  137.   inline Boolean operator<= (const CoolBignum&) const; // less than/equal
  138.   Boolean operator> (const CoolBignum&) const;    // greater than
  139.   inline Boolean operator>= (const CoolBignum&) const; // greater than/eq.
  140.  
  141.   friend ostream& operator<< (ostream&, const CoolBignum&);    // Output reference
  142.   friend ostream& operator<< (ostream&, const CoolBignum*); // Output ptr
  143.   
  144.   inline N_status status () const;        // Return CoolBignum status
  145.   void dump (ostream& = cout);            // Dump contents of CoolBignum
  146.   void print (ostream&);            // terse print
  147.  
  148. protected:
  149.   void minus_infinity (const char*) const;    // Raise - infinity exception
  150.   void plus_infinity (const char*) const;    // Raise + infinity exception
  151.   void overflow (const char*) const;        // Raise overflow error
  152.   void underflow (const char*) const;        // Raise overflow error
  153.   void no_conversion (const char*) const;    // Raise no conversion error
  154.   void divide_by_zero (const char*) const;    // Raise divide by zero
  155.  
  156. private:
  157.   Counter count;                // Number of data elements
  158.   int sign;                    // Sign of CoolBignum (+,-,or 0)
  159.   Data* data;                    // Pointer to data value
  160.   N_status state;                // Exception status
  161.  
  162.   void xtoBignum (const char *s);        // convert hex to CoolBignum
  163.   int  dtoBignum (const char *s);        // convert decimal to CoolBignum
  164.   void otoBignum (const char *s);        // convert octal to CoolBignum
  165.   void exptoBignum (const char *s);        // convert exponential to Big.
  166.  
  167.   friend int magnitude_cmp (const CoolBignum&, const CoolBignum&); // Compare mags
  168.   friend void add (const CoolBignum&, const CoolBignum&, CoolBignum&); // Unsigned add
  169.   friend void subtract (const CoolBignum&, const CoolBignum&, CoolBignum&); // Unsigned sub
  170.   friend void multiply_aux (const CoolBignum&, Data d, CoolBignum&, Counter i); 
  171.   friend Data normalize (const CoolBignum&, const CoolBignum&,
  172.              CoolBignum&, CoolBignum&);    // Normalize for division
  173.   friend void divide_aux (const CoolBignum&, Data, CoolBignum&, Data&); // Divide digit
  174.   friend Data estimate_q_hat (const CoolBignum&, const CoolBignum&, Counter); // Est quo
  175.   friend Data multiply_subtract (CoolBignum&, const CoolBignum&, Data q_hat,
  176.                 Counter);    // Multiply quotient and subt.
  177.   friend void divide (const CoolBignum&, const CoolBignum&, CoolBignum&, CoolBignum&); // Divide
  178.   void resize (Counter);            // Resize CoolBignum data
  179.   CoolBignum& trim ();                // Trim CoolBignum data
  180.   friend CoolBignumE left_shift (const CoolBignum& b1, long l);
  181.   friend CoolBignumE right_shift (const CoolBignum& b1, long l);
  182. };
  183.  
  184.  
  185. // Avoid deep copy with envelope. 
  186. // None of the operations +=... can be done in place
  187.  
  188. #define CoolLetter CoolBignum
  189. #define CoolEnvelope CoolBignumE        
  190.  
  191. #include <cool/Envelope.h>            // Include envelope macros
  192.  
  193. #undef CoolLetter
  194. #undef CoolEnvelope
  195.  
  196.  
  197. // Need and initializer to construct static bignums.
  198.  
  199. class CoolBignum_Init {
  200. public:
  201.   CoolBignum_Init ();                // Create constant Bignums
  202.   ~CoolBignum_Init();                // and destroy them once only
  203. private:
  204.   static int count;                // number of init objects created
  205. };
  206.  
  207. static CoolBignum_Init bignum_init1_s;        // trigger init of Bignums
  208.  
  209.  
  210. // 
  211.  
  212. // status -- returns status of a CoolBignum
  213. // Inputs:  none
  214. // Outputs:  status of this CoolBignum
  215. inline N_status CoolBignum::status () const {
  216.   return this->state;                // Return this->state
  217. }
  218.  
  219. // operator! -- overloaded not operator for CoolBignums
  220. // Inputs:  none
  221. // Outputs:  Boolean not of this CoolBignum
  222. inline Boolean CoolBignum::operator! () const {
  223.   return (Boolean) (this->count == 0);        // Return 1 if CoolBignum's zero
  224. }
  225.  
  226. // operator=  -- Assignment from an envelope back to real Bignum
  227. // Input:     envelope reference
  228. // Output:    Bignum reference with contents in envelope being swapped over
  229.  
  230. inline CoolBignum& CoolBignum::operator= (CoolBignumE& env){
  231.   env.shallow_swap((CoolBignumE*)this, &env);    // same physical layout
  232.   return *this;
  233. }
  234.  
  235. // operator- -- overloaded subtraction operator for CoolBignums
  236. // Inputs:  references to two CoolBignums
  237. // Outputs:  the CoolBignum difference of the two input CoolBignums
  238.  
  239. inline CoolBignumE operator- (const CoolBignum& b1, const CoolBignum& b2) {
  240.   return (b1 + (-b2));                // negate b2 and add to b1
  241. }
  242.  
  243.  
  244. // operator!= -- overloaded != comparison operator for CoolBignums
  245. // Inputs:  reference to CoolBignum
  246. // Outputs:  Boolean result of the comparison
  247. inline Boolean CoolBignum::operator!= (const CoolBignum& b) const {
  248.   return !(*this == b);                // call CoolBignum operator==
  249. }
  250.  
  251.  
  252.  
  253. // operator<= -- overloaded <= operator for CoolBignums
  254. // Inputs:  reference to CoolBignum
  255. // Outputs:  Boolean result of <= comparison
  256. inline Boolean CoolBignum::operator<= (const CoolBignum& b) const {
  257.   return !(*this > b);                // call CoolBignum operator>
  258. }
  259.  
  260.  
  261.  
  262. // operator>= -- overloaded >= operator for CoolBignums
  263. // Inputs:  reference to CoolBignum
  264. // Outputs:  Boolean result of >= comparison
  265. inline Boolean CoolBignum::operator>= (const CoolBignum& b) const {
  266.   return !(*this < b);            
  267. }
  268.  
  269.  
  270.  
  271. // operator+= -- overloaded addition assignment operator for CoolBignums
  272. // Inputs:  reference to CoolBignum
  273. // Outputs:  reference to modified CoolBignum
  274. inline CoolBignum& CoolBignum::operator+= (const CoolBignum& b) {
  275.   *this = *this + b;                // call CoolBignum operator+
  276.   return *this;
  277. }
  278.  
  279.  
  280.  
  281. // operator-= -- overloaded subtraction assignment operator for CoolBignums
  282. // Inputs:  reference to CoolBignum
  283. // Outputs:  reference to modified CoolBignum
  284. inline CoolBignum& CoolBignum::operator-= (const CoolBignum& b) {
  285.   *this = *this - b;                // call CoolBignum operator-
  286.   return *this;
  287. }
  288.  
  289.  
  290.  
  291. // operator*= -- overloaded multiplication assignment operator for CoolBignums
  292. // Inputs:  reference to CoolBignum
  293. // Outputs:  reference to modified CoolBignum
  294. inline CoolBignum& CoolBignum::operator*= (const CoolBignum& b) {
  295.   *this = *this * b;                // call CoolBignum operator*
  296.   return *this;
  297. }
  298.  
  299.  
  300.  
  301. // operator/= -- overloaded division assignment operator for CoolBignums
  302. // Inputs:  reference to CoolBignum
  303. // Outputs:  reference to modified CoolBignum
  304. inline CoolBignum& CoolBignum::operator/= (const CoolBignum& b) {
  305.   *this = *this / b;                // call CoolBignum operator/
  306.   return *this;
  307. }
  308.  
  309.  
  310.  
  311. // operator%= -- overloaded modulus assignment operator for CoolBignums
  312. // Inputs:  reference to CoolBignum
  313. // Outputs:  reference to modified CoolBignum
  314. inline CoolBignum& CoolBignum::operator%= (const CoolBignum& b) {
  315.   *this = *this % b;                // call CoolBignum operator%
  316.   return *this;
  317. }
  318.  
  319.  
  320.  
  321. // operator<<= -- overloaded left shift assignment operator for CoolBignums
  322. // Inputs:  reference to CoolBignum
  323. // Outputs:  reference to modified CoolBignum
  324. inline CoolBignum& CoolBignum::operator<<= (const CoolBignum& b) {
  325.   *this = *this << long(b);            // call CoolBignum operator<<
  326.   return *this;
  327. }
  328.  
  329.  
  330.  
  331. // operator>>= -- overloaded right shift assignment operator for CoolBignums
  332. // Inputs:  reference to CoolBignum
  333. // Outputs:  reference to modified CoolBignum
  334. inline CoolBignum& CoolBignum::operator>>= (const CoolBignum& b) {
  335.   *this = *this >> long(b);            // call CoolBignum operator>>
  336.   return *this;
  337. }
  338.  
  339.  
  340.  
  341. // operator<< -- output operator for pointers to CoolBignums
  342. inline ostream& operator<< (ostream& os, const CoolBignum* b) {
  343.   if (b) os << *b;                // call CoolBignum output operator
  344.   return os;                    
  345. }
  346.  
  347. #endif BIGNUMH                    // End BIGNUMH
  348.  
  349.